#pragma once
#include<iostream>
#include<math.h>
#include<vector>
using namespace std;
#define Pai acos(-1);

vector<double> Newton_formula(int n,vector<double> f,vector<double> x){
    vector<vector<double> > pai(n+1, vector<double>(n+1));
    for (int i = 0; i <=n; i++)
    {
        pai[i][0]=1;
    }
    for (int i = 1; i <=n; i++)
    {
        pai[i][i]=-x[i]*pai[i-1][i-1];
        for (int j = 1; j <i; j++)
        {
            pai[i][j]=-x[i]*pai[i-1][j-1]+pai[i-1][j];
        }
        
    }
    vector<vector<double> >F(n+1, vector<double>(n+1));
    for (int i = 0; i <= n; i++)
    {
        F[i][0]=f[i];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <=i; j++){
            F[i][j]=(F[i][j-1]-F[i-1][j-1])/(x[i]-x[i-j]);
        }
    }
    for (int i = 0; i <=n; i++)
    {
        
        for (int j = 0; j <=i; j++)
        {
            pai[i][j]=F[i][i]*pai[i][j];
        }
        
    }
    vector<double>p(n+1);
    for (int i = 0; i <=n; i++){
        for (int j = 0; j <=n-i; j++){
            p[i]+=pai[i+j][j];
        }
    }
    return p;
}
void functionB(int n){
    vector<double>x(n+1);
    for (int i = 0; i <=n; i++)
        x[i]=-5+10*i/n;
    vector<double>f(n+1);
    for (int i = 0; i <=n; i++)
        f[i]=1/(1+x[i]*x[i]);
    vector<double>p;
    p=Newton_formula(n,f,x);
    cout<<"以下为升幂排列的函数系数"<<endl;
    for (int i = 0; i <n; i++){
        cout<<p[i]<<" ";
    }
     cout<<p[n]<<endl;
}
void functionC(int n){
    vector<double>x(n);
    for (int i = 0; i <n; i++)
    x[i]=cos((2*i+1)/(2*n));
    vector<double>f(n);
    for (int i = 0; i <n; i++)
        f[i]=1/(1+25*x[i]*x[i]);
    vector<double>p;
    p=Newton_formula(n,f,x);
}
vector<double>  hermite(int n,vector<double>x,vector<double>f,vector<double>df){
    vector<vector<double> > pai(2*(n+1), vector<double>(2*(n+1)));
    vector<vector<double> > F(2*(n+1), vector<double>(2*(n+1)));
    vector<double>f_t(2*(n+1));
    for (int i = 0; i <=n; i++){
        f_t[2*i]=f[i];
        f_t[2*i+1]=f[i];
    }
    f=f_t;
    for (int i = 0; i <=2*n+1; i++)
    {
        pai[i][0]=1;
    }
    for (int i = 1; i <=2*n+1; i++)
    {
        pai[i][i]=-x[i]*pai[i-1][i-1];
        for (int j = 1; j <i; j++)
        {
            pai[i][j]=-x[i]*pai[i-1][j-1]+pai[i-1][j];
        }
        
    }
    for (int i = 0; i <= n; i++)
    {
        F[2*i][0]=f[2*i];
        F[2*i+1][0]=f[2*i+1];
        F[2*i+1][1]=df[i];
    }
    for (int i = 1; i <= n; i++)
    {   
        for (int j = 1; j <=i; j++){
            F[2*i][2*j-1]=(F[2*i][2*j-2]-F[2*i-1][2*j-2])/(x[2*i]-x[2*(i-j)+1]);
            F[2*i][2*j]=(F[2*i][2*j-1]-F[2*i-1][2*j-1])/(x[2*i]-x[2*(i-j)]);
            F[2*i+1][2*j]=(F[2*i][2*j-1]-F[2*i-1][2*j-1])/(x[2*i+1]-x[2*(i-j)+1]);
            F[2*i+1][2*j+1]=(F[2*i][2*j-1]-F[2*i-1][2*j-1])/(x[2*i+1]-x[2*(i-j)]);
        }
    }
    for (int i = 0; i <=2*n+1; i++)
    {
        
        for (int j = 0; j <=i; j++)
        {
            pai[i][j]=F[i][i]*pai[i][j];
        }
        
    }
    vector<double>p(2*(n+1));
    for (int i = 0; i <=2*n+1; i++){
        for (int j = 0; j <=n-i; j++){
            p[i]+=pai[i+j][j];
        }
    }
    return p;
}
void print_vector(vector<double>p,int n){
    cout<<"以下为升幂排列的函数系数"<<endl;
    for (int i = 0; i <n; i++){
        cout<<p[i]<<" ";
    }
     cout<<p[n]<<endl;
}
double using_vector(vector<double>p,double x,int n){
    double sum=p[0];
    double xn=x;
    for (int i = 1; i <n; i++){
        sum+=p[i]*xn;
        xn*=x;
    }
    return sum;
}